/*
 * @lc app=leetcode id=5 lang=cpp
 *
 * [5] Longest Palindromic Substring
 */
class Solution {
public:
    string longestPalindrome(string s) {

        int len = s.size();
        if (len < 2) {
            return s;
        }

        int maxLen = 1;
        int startIdx = 0;

        vector<vector<bool>> memo(len, vector<bool>(len, false));
        for (int i=0; i<len; i++) {
            memo[i][i] = true;
        }

        int gap = 1;
        for (; gap < len; gap++) {
            for (int i=0, j=i+gap; i<len && j<len; i++, j++) {
                if (j > i+1) {
                    memo[i][j] = memo[i+1][j-1] && (s[i] == s[j]);
                } else {
                    memo[i][j] = (s[i]==s[j]);
                }
                if (memo[i][j]) {
                    if (j-i+1 > maxLen) {
                        maxLen = j-i+1;
                        startIdx = i;
                    }
                }
            }
        }

        return s.substr(startIdx, maxLen);
    }
};

